package ac

import (
//"fmt"
)

type TrieNode struct {
	children map[rune]*TrieNode
	fail     *TrieNode
	length   int
}

func NewTrieNode() *TrieNode {
	return &TrieNode{
		children: make(map[rune]*TrieNode),
		length:   -1,
	}
}

type ACAutomaton struct {
	root *TrieNode
}

func NewACAutomaton() *ACAutomaton {
	return &ACAutomaton{root: NewTrieNode()}
}

func (ac *ACAutomaton) AddWord(word string) {
	node := ac.root
	codes := []rune(word)
	for _, ch := range codes {
		if _, ok := node.children[ch]; !ok {
			node.children[ch] = NewTrieNode()
		}
		node = node.children[ch]
	}
	node.length = len(codes)
}

func (ac *ACAutomaton) Build() {
	queue := make([]*TrieNode, 0)
	ac.root.fail = nil
	queue = append(queue, ac.root)
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		for ch, child := range node.children {
			failNode := node.fail
			for failNode != nil && failNode.children[ch] == nil {
				failNode = failNode.fail
			}
			if failNode == nil {
				child.fail = ac.root
			} else {
				child.fail = failNode.children[ch]
			}
			queue = append(queue, child)
		}
	}
}

func (ac *ACAutomaton) Replace(text []rune, replace rune) string {
	res := text
	node := ac.root
	for i, char := range text {
		child, ok := node.children[char]
		for node != ac.root && !ok {
			node = node.fail
			child, ok = node.children[char]
		}
		node = child
		if node == nil {
			node = ac.root
		}
		if node.length != -1 && i+1 >= node.length {
			for j := i + 1 - node.length; j < i+1; j++ {
				res[j] = replace
			}
			node = ac.root
		}
	}
	return string(res)
}

//func main() {
//ac := NewACAutomaton()
//ac.AddWord("中国")
//ac.AddWord("中国人")
//ac.AddWord("中国小说网")
//ac.Build()

//fmt.Println("res:", ac.Replace("我是中国人民共和国公民", '*'))
//}
